package _022_2_12

//time limit
func maxSubArray2(nums []int) int {
	max := nums[0]
	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j]

			if sum > max {
				max = sum
			}
		}
	}

	return max
}

func maxSubArray(nums []int) int {
	max := nums[0]
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		if dp[i-1] > 0 {
			dp[i] += dp[i-1]
		} else {
			dp[i] = nums[i]
		}
	}
	max = dp[0]
	for i := 1; i < len(dp); i++ {
		if dp[i] > max {
			max = dp[i]
		}
	}

	return max
}
